package sort;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/11/6 9:47
 * 插入排序
 *
 */
import java.util.Arrays;

public class InsertSort {
    /**
     * 插入排序
     * 时间复杂度：
     * 最好情况：O(n) 当 数组已经有序
     * 最坏情况：O(n^2) 当 数据是逆序
     * 平均情况：O(n^2)
     * 对于插入排序，数组越趋于有序，耗时越少
     *
     * 空间复杂度：
     * 最好/平均/最坏：O(1)
     *
     * 稳定性：稳定
     * @param array
     */
    public static void insert2(long[] array) {
        for (int i = 1; i < array.length; i++) {    // 循环 n - 1 次
            // 有序区间: [0, i)
            // 无序区间: [i, array.length)

            long x = array[i];
            int j;
            for (j = i - 1; j >= 0 && array[j] > x; j--) {
                array[j + 1] = array[j];
            }

            array[j + 1] = x;
        }
    }

    public static void insertSort(long[] array) {
        // 要对 array.length 个元素做排序，需要多少次 查找+插入 的过程？
        // array.length - 1

        // 外层的循环：需要进行很多次的 查找+插入
        for (int i = 0; i < array.length - 1; i++) {
            // 有序区间
            // 第一次（i == 0）： [0, 0] / [0, 1)
            // 第二次（i == 1）： [0, 1] / [0, 2)
            // ...
            // 第 i - 1 次（i）： [0, i] / [0, i + 1)

            // 有序区间：[0, i]
            // 无序区间：[i + 1, array.length)
            // 要插入的元素的下标是无序区间的第一个元素（紧挨着有序区间的下一个元素）
            long x = array[i + 1];

            // 查找并插入，遍历整个有序区间: [0, i]
            int j;
            for (j = i; j >= 0 && array[j] > x; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = x;
        }
    }
    public static void 查找并插入整理(long[] array, int index){
        long x = array[index];

        int i ;
        for (i = index - 1; i >= 0 && array[i]>x; i--) {
            array[i + 1] = array[i];
        }
        array[i + 1] = x;
    }
    public static void 查找并插入(long[] array, int index) {
        // [0, index) 有序的
        // [index] 这个下标的元素就是要被插入的元素

        long x = array[index];
        // 从后往前进行 有序区间 的遍历
        int i;
        for (i = index - 1; i >= 0; i--) {
            long e = array[i];

            if (e > x) {
                // 说明 x 应该插入到 e 的前面去（并不一定挨着）
                // 把 e 往后搬，给 x 腾地方
                array[i + 1] = array[i];
            } else {
                // 说明 x 应该插入到 e 的后边（紧挨着）
                // e 的下标是 i，紧挨着的下标是 i + 1
                array[i + 1] = x;
                // x 已经成功找到合适的位置并且插入了，不需要继续遍历有序区间了
                break;
            }
        }

        // 如果整个区间都遍历完之后，x 还是没有找到合适的位置，说明 x 比第一个元素还小
        // 把 x 放在最开始
        // 当上述循环因为这个条件（i >= 0）不满足结束的循环，则 i 一定是 -1
        // 否则，一定是由于 break 退出的循环，则 i >= 0
        if (i == -1) {
            array[0] = x;
        }
    }

    public static void main(String[] args) {
        long[] array = {1, 2, 3, 5, 6, 8, 9, 0};

        查找并插入(array, 7);

        System.out.println(Arrays.toString(array));
    }

    // 有序区间: [from, to)
    public static void insertSort递归版本(long[] array, int from, int to) {
        int size = to - from;   // 有序区间的长度
        // 无序区间的长度 array.length - size
        if (array.length - size <= 1) {
            return;
        }

        // [from, to)
        // 要插入的元素一定在 [to]
        long x = array[to];
        int i;
        for (i = to - 1; i >= 0 && array[i] > x; i--) {
            array[i + 1] = array[i];
        }

        array[i + 1] = x;

        // [from, to + 1) 有序了
        insertSort递归版本(array, from, to + 1);
    }

}
